Fibonacci Fun

By:

Alex Moore

Many of us know the Fibonacci sequence, not because of how famous it is, but because its so easy to remember. To get the next term in the sequence we simply add the two previous terms. Lets make this more precise. A real sequence is a function from the nonnegative integers, {0,1,2,3,…}, into the real numbers. Let f be the Fibonacci sequence, that is, define f(0)=1 and f(1)=1. Then, given f(0), f(1), …, f(n), we define the Fibonacci sequence recursively as f(n+1)=f(n)+f(n-1). While this sequence is easy to compute, the terms get large rather quickly. Below are the first 30 terms of the sequence.

A natural thing to ask is do the ratio of consecutive terms converge to a number? Below is the ratio of terms by use of Excel.

It seems as though the ratio of terms does not change for n>20. This is good evidence that we have convergence but this is not a proof. Let us attempt to prove this converges, and if so, to what number. Let lim denote the limit as n increases to infinity and let L denote the limit. Then we have:

L = lim f(n+1)/f(n)=

lim (f(n)+f(n-1))/f(n)=

lim (f(n)/f(n) + f(n-1)/f(n))=

lim 1+f(n-1)/f(n) =

1 + lim f(n-1)/f(n) =

1+ 1/L.

Therefore, we know the limit of the ratios satisfies the equation L = 1 + 1/L. By multiplying the equation by L we get L² = L+1 which is the same as L² –L-1=0. This is another famous equation. The roots of this equation are r and 1-r, where r is the golden ratio

r = ½ +sqrt(5)/2.

Clearly f(n+1)/f(n) is greater than 0 since f(n+1) = f(n) + f(n-1) > f(n) and so our limit is r since 1-r <0. What is we took the ratio of every second term, that is, f(n+2)/f(n) ? Do these ratios converge? If so, to what number does it converge? Let us get an idea of the behavior. Column 4 is the ratio of each second term.

Once again it appears that these ratios are converging since the ratios for n>22 do not appear to be changing. Let us follow the same procedure as before. Let L be the limit.

L = lim f(n+2)/f(n) =

lim (f(n+1)+f(n))/f(n) =

lim f(n+1)/f(n) + f(n)/f(n) =

lim f(n+1)/f(n) +1 =

1 + lim f(n+1)/f(n) =

1+r.

Using the result from above we see that the limit is 1+r! This is interesting. Suppose we let L_k be the limit of the ratio of every k^th term, that is L_k = lim f(n+k)/f(n). Then,

L_k+1 = lim f(n+(k+1))/f(n) =

lim (f(n+k)+f(n+k-1))/f(n) =

lim f(n+k)/f(n) + f(n+k-1)/f(n) =

lim f(n+k)/f(n) + lim f(n+k-1)/f(n) =

L_k + L_k-1.

Wow! These limits follow a similar structure that the Fibonacci sequence follows! Is this surprising? It probably should not be but it is neat! Is there a nice closed form for these numbers? Lets see:

L₁ = r

L₂ = 1+r

L₃ = L₂ + L₁ = 1+2r

L₄ = L₃ + L₂ = 2+3r

L₅ = L₄ + L₃ = 3+5r

The pattern appears to be following L_k = f(k-2) + r f(k-1)!

The final aspect of this sequence we will look at is: is there a closed (possibly continuous) function g(x) such that f restricted to the nonnegative integers is the Fibonacci sequence? That is, is there a function f(x) such that g(n)=f(n) for all nonnegative integers n? Yes! By use of eigenvector and eigenvalue methods of linear algebra we have the formula

g(x) = (r^x+1 - (1-r)^x+1)/sqrt(5).

What does the graph of this horrendous function g(x) look like? Since there is a limiting constant of the ratios I would expect that the graph to look similar to h(x) = r^x. Lets look!

This graph certain does have the look of an exponential graph, just as we expected!